package com.desheng.bigdata.ds.stack;

/**
 * 利用栈处理逆波兰表达式的问题
 * 中缀表达式： 3 * （17 - 15） + 18 / 6
 * 逆波兰表达式（后缀表达式）: 3 17 15 - * 18 6 / +
 */
public class ReversePolishNotation {

    public static void main(String[] args) {
        String[] notations = {"3", "17", "15", "-", "*", "18", "6", "/", "+"};
        int result = calcReversePolish(notations);
        System.out.println("结果为： " + result);
    }

    private static int calcReversePolish(String[] notations) {
        Stack<Integer> stack = new Stack<>();
        if(notations == null || notations.length == 0) {
            return 0;
        }

        for(String notation : notations) {
            char ch = notation.charAt(0);
            if(isDigital(ch)) {
                stack.push(Integer.valueOf(notation));
            } else {
               if(!stack.isEmpty()) {
                   int right = stack.pop();
                   int left = stack.pop();
                   int result = 0;
                   switch (ch) {
                       case '+':
                           result = left + right;
                           break;
                       case '-':
                           result = left - right;
                           break;
                       case '/':
                           result = left / right;
                           break;
                       case '*':
                           result = left * right;
                           break;
                   }
                   stack.push(result);
               }
            }
        }
        return stack.pop();
    }

    private static boolean isDigital(char chs) {
        return chs >= '0' && chs <= '9';
    }
}
